package weekMatch.one_342;

import java.io.ObjectInputStream;

public class LeeCode_04 {
    public static void main(String[] args) {
//        System.out.println(minOperations(new int[]{2, 6, 3, 4}));
//        System.out.println(minOperations(new int[]{2, 10, 6, 14}));
        System.out.println(minOperations(new int[]{10,5,10,30,70,4,2,6,8,4}));

    }
    private static int minOperations(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int num : nums) {
            if (num == 1)
                count++;
        }
        if (count > 0){
            return n - count;
        }
        for (int i = 0; i < n - 1; i++) {
            if (getMax(nums[i], nums[i + 1]) == 1){
                return n;
            }
        }
        count = 0;
        int[] t = nums;
        int[] tmp = new int[t.length - 1];
        while (tmp.length > 0){
            count++;
            for (int i = 0; i < t.length - 1; i++) {
                tmp[i] = getMax(t[i], t[i + 1]);
                if (tmp[i] == 1){
                    return count + n - 1;
                }
            }
            t = tmp;
            tmp = new int[t.length - 1];
        }
        return -1;
    }
    private static int getMax(int a, int b){
        while (a != 0 && b != 0){
            int ta = a, tb = b;
            a = Math.max(ta, tb);
            b = Math.min(ta, tb);
            a = a % b;
        }
        if (a == 0)
            return b;
        else
            return a;
    }
}
